#include <stdio.h>
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//void Insertsort(int* a, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		// [0, end] end+1
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				--end;
//			}
//			else
//			{
//				break;
//			}
//		}
//
//		a[end + 1] = tmp;
//	}
//}

//void Insertsort(int* a, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < a[end])
//			{
//				a[end + 1] = a[end];
//				end--;
//			}
//			else
//				break;
//		}
//		a[end + 1] = tmp;
//	}

	void Shellsort(int* a, int n)
	{
		int gap = n;
		while (gap > 1)
		{
			gap /= 2;
			for(int i = 0;i<n-gap;i++)
				{
					 int end = i;
				   int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
				}
		}
	}




int main()
{
	int arr[] = { 1,3,6,4,7,9,8,2,15,22,20,10};
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
		
	}
	printf("\n");
	//Insertsort(arr, sizeof(arr) / sizeof(arr[0]));
	Shellsort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}